Engineers and designers use computer aided design (CAD) systems to generate drawings and designs. Using a graphic editor, a user of the system specifies the components of a drawing with input devices such as a keyboard and a mouse. The resulting drawing can be rendered on a display device or a printer for viewing. In some sophisticated systems, the drawings may directly drive a manufacturing process to produce the object depicted in the drawing. The drawing's specifications typically are stored in a memory of the CAD system. The specifications can include the general geometric shape of the drawing's components, and any additional constraints which are to be applied when rendering the drawing.
The constraints allow a user to limit the possible configurations of a drawing while the components are manipulated in real-time. For example, to draw an equilateral triangle with a graphic editor, the user first draws any arbitrary triangle, i.e., three lines connected at their ends. Then, the user constrains the sides of the triangle to be equal. By specifying the constraints, the triangle can be freely manipulated, for example, according to size and orientation, while retaining its correct equilateral shape. Similarly, other geometric shapes can be added, and constraints relating the components can be added to reflect the designer's overall intent.
A constraint solver is typically used to maintain the geometric relationships of the drawing's components according to the user specified constraints. The constraint solver determines values for various component variables used in the constraints so that the geometric relationships of the various components remain consistent, no matter how the components are arranged.
In some cases, the components of the drawing are redundantly constrained by the user. For example, an equilateral triangle is redundantly constrained when the user specifies that all sides need to be equal, and also, that all angles of the triangle need to be equal. This is a trivial case, which is unlikely to happen in practice.
However, in a drawing including many complex geometric components of various shapes and configurations, imagine an aircraft frame, even a skilled user will have great difficulty deducing the absolute minimum number of constraints required to exactly define the desired configuration of the components. Avoiding the specification of redundant constraints may require the burdensome task of proving many obscure theorems in Euclidean geometry. In this case, the conservative, and perhaps lazy user is likely to add unnecessary redundant constraints to the drawing.
In the prior art, redundant constraints have been difficult to solve, and can consume a large amount of processing time, making known graphic editors cumbersome to use. In many cases, the redundant constraints totally confuse the solver, causing it not to find any solution. Therefore, it is desired to provide a graphic editor which can efficiently solve a redundantly constrained drawing.